package behavior;

import arena.Node;
import java.util.LinkedList;
import java.util.List;

/**
 * BFSBehavior implements a breadth-first graph searching algorithm
 * which is used to send a robot to a specific node in an efficient manner
 *
 * @author      Gabriel Loewen
 * @author      James Weston
 * @author      Jackie O'Quinn
 */
public class BFSBehavior extends Behavior {

    /**
     *List to hold the path.
     */
    private LinkedList<Node> path = new LinkedList<Node>();
    private double progress = 0;

    /**
     * Default constructor
     */
    public BFSBehavior() {
        super("BFS");
    }

    public boolean isValidInput(String input) {
        return robot.getArena().nodeMap.containsKey(input);
    }

    public boolean isValidMove() {
        if (!path.peek().isOccupied) {
            return true;
        }
        path.clear();
        return false;
    }

    /**
     * Calculates the path through the nodes using the BFS algorithm
     * and populates a queue with the moves necessary to complete the
     * path
     *
     * @param   goal    The destination in (x,y) format.  i.e. "4,3" would
     * specify a goal of the coordinate (4,3).
     * @param   cancel  Boolean variable that cancels the algorithm if the user
     * presses the cancel button.
     */
    public void getPath(String goal, boolean cancel) {

        if (!nodeExists(goal) || cancel) {
            return;
        }

        Node startNode = robot.getArena().nodeMap.get(robot.getLocation().toString());
        Node goalNode = robot.getArena().nodeMap.get(goal);

        // list of visited nodes
        LinkedList closedList = new LinkedList();

        // list of nodes to visit (sorted)
        LinkedList openList = new LinkedList();
        openList.add(startNode);
        System.out.println(startNode);
        startNode.pathParent = null;

        int iterations = 0;
        while (!openList.isEmpty()) {
            Node node = (Node) openList.removeFirst();
            iterations++;
            progress = ((double) iterations / (double) (robot.getArena().height * robot.getArena().width)) * 100.0;
            if (node.getLocation().toString().equals(goalNode.toString())) {
                progress = 100;
                constructPath(goalNode);
                return;
            } else {
                closedList.add(node);
                // add neighbors to the open list
                List<Node> adjList = Node.getAdjNodes(node);
                for (Node neighborNode: adjList) {
                   if (!closedList.contains(neighborNode) &&
                            !openList.contains(neighborNode) &&
                            !neighborNode.isOccupied &&
                            nodeExists(neighborNode.toString())) {
                        neighborNode.pathParent = node;
                        openList.addLast(neighborNode);
                    }
                }
            }
        }
        // no path found
    }

    /**
     * Constructs a path from the robots current position to the input node.
     *
     * @param   node    The destination node object.
     */
    protected void constructPath(Node node) {
        while (node.pathParent != null) {
            path.addFirst(node);
            node = node.pathParent;
        }
    }

    /**
     * Returns a boolean value for whether or not a move is waiting to be
     * executed.
     */
    public boolean hasMove() {
        return !path.isEmpty();
    }

    /**
     * Returns an integer array containing the data needed for the
     * next move in the queue.
     *
     * @see Util
     */
    public int[] nextMove() {
        Node node = path.pop();
        int dx = node.getLocation().x - robot.getLocation().x;
        int dy = node.getLocation().y - robot.getLocation().y;

        char dir;
        if (dx == 0) {
            if (dy > 0) {
                dir = 'N';
            } else {
                dir = 'S';
            }
        } else {
            if (dx > 0) {
                dir = 'E';
            } else {
                dir = 'W';
            }
        }

        return Util.getMoveData(robot.heading, robot.getLocation().x, robot.getLocation().y, dir);
    }

    private void printPath() {
        System.out.print("Printing path: ");
        for (Node node: path) {
            System.out.print(node + " : ");
        }
        System.out.println();
    }

    public boolean requiresCompass() {
        return false;
    }

    public boolean requiresTarget() {
        return true;
    }

    @Override
    public double getProgress() {
        return progress;
    }

    @Override
    public void resetProgress() {
        progress = 0;
    }
}
